from BinaryTree import *
class Solution:
	# @param {TreeNode} root
	# @return {integer}
	def maxPathSum(self, root):
		ans = [root.val]
		self.__longest(root, ans)
		return ans[0]

	def __longest_path_down(self, root, ans):
		if root is None:
			return 0
		ll = self.__longest_path_down(root.left, ans)
		rr = self.__longest_path_down(root.right, ans)
		ans[0] = max(ans[0], ll+rr+node.val)
		

if __name__ == '__main__':
	t = BinaryTree([-2, 1])
	t.display()
	print Solution().maxPathSum(t.tree())